{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"top\"></a><img src=\"images/chisel_1024.png\" alt=\"Chisel logo\" style=\"width:480px;\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Module 2.2: Combinational Logic\n",
    "**Prev: [Your First Chisel Module](2.1_first_module.ipynb)**<br>\n",
    "**Next: [Control Flow](2.3_control_flow.ipynb)**\n",
    "\n",
    "## Motivation\n",
    "In this section you will see how to use Chisel components to implement combinational logic.\n",
    "We will demonstrate how three of the basic Chisel types: `UInt `- unsigned integer; `SInt` - signed integer, and `Bool` - true or false may be connected and operated upon.\n",
    "Notice how all Chisel variables are declared as Scala `val`s.\n",
    "Never use a Scala `var` for a hardware construct, since the construct itself may never change once defined; only its value may change when running the hardware.\n",
    "Wires may be used for parameterized types.\n",
    "\n",
    "## Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val path = System.getProperty(\"user.dir\") + \"/source/load-ivy.sc\"\n",
    "interp.load.module(ammonite.ops.Path(java.nio.file.FileSystems.getDefault().getPath(path)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chisel3._\n",
    "import chisel3.util._\n",
    "import chisel3.tester._\n",
    "import chisel3.tester.RawTester.test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Common Operators\n",
    "Now that you understand how `Module`s are constructed, let's make some hardware! Take a look at the empty module below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyModule extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in  = Input(UInt(4.W))\n",
    "    val out = Output(UInt(4.W))\n",
    "  })\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've called our class `MyModule`, and it extends `Module`. This means it gets mapped to a hardware module in Verilog. Our `MyModule` module has one input and one output. The input is a 4-bit unsigned integer (`UInt`), and so is the output. \n",
    "\n",
    "<span style=\"color:blue\">**Example: Scala and Chisel Operators Look the Same**</span><br>\n",
    "Let's look at different operations we can perform on data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyModule extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in  = Input(UInt(4.W))\n",
    "    val out = Output(UInt(4.W))\n",
    "  })\n",
    "\n",
    "  val two  = 1 + 1\n",
    "  println(two)\n",
    "  val utwo = 1.U + 1.U\n",
    "  println(utwo)\n",
    "  \n",
    "  io.out := io.in\n",
    "}\n",
    "println(getVerilog(new MyModule))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create two `val`s. The first adds two Scala `Int`s, so `println` prints out the integer 2. The second `val` adds two *Chisel* `UInt`s together, so `println` sees this as a hardware node and prints out the type name and pointer (`chisel3.core.UInt@d`). Note that `1.U` is a type cast from a Scala `Int` (1) to a Chisel `UInt` literal.\n",
    "\n",
    "We need to drive the output to something, so we just connect it to the input for now, as with the passthrough module in the previous tutorial.\n",
    "\n",
    "<span style=\"color:blue\">**Example: Incompatible Operation**</span><br>\n",
    "What happens if we add a Chisel `1.U` to the literal `1`? These types are incompatible, as the former is a hardware wire of value 1, while the latter is a Scala value of 1. So Chisel will give a type mismatch error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyModuleTwo extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in  = Input(UInt(4.W))\n",
    "    val out = Output(UInt(4.W))\n",
    "  })\n",
    "\n",
    "  val twotwo = 1.U + 1\n",
    "  println(twotwo)\n",
    "  \n",
    "  io.out := io.in\n",
    "}\n",
    "println(getVerilog(new MyModuleTwo))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's important to remember the distinction between types when performing operations. Scala is a strongly typed language, so any type casting must be explicit.\n",
    "\n",
    "<span style=\"color:blue\">**Example: More Chisel Operators**</span><br>\n",
    "Other common operations are subtraction and multiplication. These are handled on unsigned integers as expected. Let's  see these in action. We show the Verilog, though there's some underlying Chisel features that obfuscate the simple code we would expect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyOperators extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in      = Input(UInt(4.W))\n",
    "    val out_add = Output(UInt(4.W))\n",
    "    val out_sub = Output(UInt(4.W))\n",
    "    val out_mul = Output(UInt(4.W))\n",
    "  })\n",
    "\n",
    "  io.out_add := 1.U + 4.U\n",
    "  io.out_sub := 2.U - 1.U\n",
    "  io.out_mul := 4.U * 2.U\n",
    "}\n",
    "println(getVerilog(new MyOperators))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here's a sample tester for the above operations. Instead of using an anonymous tester class like in the previous tutorial, we'll create an explicit tester class. This is just an alternative way of writing a tester."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test(new MyOperators) {c =>\n",
    "  c.io.out_add.expect(5.U)\n",
    "  c.io.out_sub.expect(1.U)\n",
    "  c.io.out_mul.expect(8.U)\n",
    "}\n",
    "println(\"SUCCESS!!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:blue\">**Example: Mux and Concatenation**</span><br>\n",
    "In addition to addition, subtraction, and multplication, Chisel has mux and concatenation operators. These are shown below. The `Mux` operates like a traditional ternary operator, with the order (select, value if true, value if false). Note that `true.B` and `false.B` are the preferred ways to create Chisel Bool literals. The `Cat` ordering is MSB then LSB (where B refers to bit or bits), and only takes two arguments. Concatenating more than two values requires multiple `Cat` calls or advanced Chisel and Scala features covered in later sections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyOperatorsTwo extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in      = Input(UInt(4.W))\n",
    "    val out_mux = Output(UInt(4.W))\n",
    "    val out_cat = Output(UInt(4.W))\n",
    "  })\n",
    "\n",
    "  val s = true.B\n",
    "  io.out_mux := Mux(s, 3.U, 0.U) // should return 3.U, since s is true\n",
    "  io.out_cat := Cat(2.U, 1.U)    // concatenates 2 (b10) with 1 (b1) to give 5 (101)\n",
    "}\n",
    "\n",
    "println(getVerilog(new MyOperatorsTwo))\n",
    "\n",
    "test(new MyOperatorsTwo) { c =>\n",
    "  c.io.out_mux.expect(3.U)\n",
    "  c.io.out_cat.expect(5.U)\n",
    "}\n",
    "println(\"SUCCESS!!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Notice how the Verilog contains constants instead of actual mux or concatenation logic. This is because FIRRTL transformations have simplified the circuit, eliminating obvious logic. \n",
    "\n",
    "For a more complete list of Chisel operators, see the [Chisel cheatsheet](https://github.com/freechipsproject/chisel-cheatsheet/releases/latest/download/chisel_cheatsheet.pdf). For the most complete list of operators and their implementation details, look through the [Chisel API](https://chisel-lang.org/api/latest/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Exercises\n",
    "To complete these exercises, you may need to look through the [Chisel cheatsheet](https://github.com/freechipsproject/chisel-cheatsheet/releases/latest/download/chisel_cheatsheet.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">**Exercise: MAC**</span><br>\n",
    "Create a Chisel module that implements the multiply accumulate function, `(A*B)+C`, and passes the testbench."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MAC extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in_a = Input(UInt(4.W))\n",
    "    val in_b = Input(UInt(4.W))\n",
    "    val in_c = Input(UInt(4.W))\n",
    "    val out  = Output(UInt(8.W))\n",
    "  })\n",
    "\n",
    "  ???\n",
    "}\n",
    "\n",
    "test(new MAC) { c =>\n",
    "  val cycles = 100\n",
    "  import scala.util.Random\n",
    "  for (i <- 0 until cycles) {\n",
    "    val in_a = Random.nextInt(16)\n",
    "    val in_b = Random.nextInt(16)\n",
    "    val in_c = Random.nextInt(16)\n",
    "    c.io.in_a.poke(in_a.U)\n",
    "    c.io.in_b.poke(in_b.U)\n",
    "    c.io.in_c.poke(in_c.U)\n",
    "    c.io.out.expect((in_a * in_b + in_c).U)\n",
    "  }\n",
    "}\n",
    "println(\"SUCCESS!!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-1\" />\n",
    "<label for=\"check-1\"><strong>Solution</strong></label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "class MAC extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in_a = Input(UInt(4.W))\n",
    "    val in_b = Input(UInt(4.W))\n",
    "    val in_c = Input(UInt(4.W))\n",
    "    val out  = Output(UInt(8.W))\n",
    "  })\n",
    "\n",
    "  io.out := (io.in_a * io.in_b) + io.in_c\n",
    "}\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<span style=\"color:red\">**Exercise: Arbiter**</span><br>\n",
    "The following circuit arbitrates data coming from a FIFO into two parallel processing units. The FIFO and processing elements (PEs) communicate with ready-valid interfaces. Construct the arbiter to send data to whichever PE is ready to receive data, prioritizing PE0 if both are ready to receive data. Remember that the arbiter should tell the FIFO that it's ready to receive data when at least one of the PEs can receive data. Also, wait for a PE to assert that it's ready before asserting that the data are valid. You will likely need binary operators to complete this exercise.\n",
    "\n",
    "<img src=\"images/arbiter.png\" width=\"687\" height=\"177\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Arbiter extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    // FIFO\n",
    "    val fifo_valid = Input(Bool())\n",
    "    val fifo_ready = Output(Bool())\n",
    "    val fifo_data  = Input(UInt(16.W))\n",
    "    \n",
    "    // PE0\n",
    "    val pe0_valid  = Output(Bool())\n",
    "    val pe0_ready  = Input(Bool())\n",
    "    val pe0_data   = Output(UInt(16.W))\n",
    "    \n",
    "    // PE1\n",
    "    val pe1_valid  = Output(Bool())\n",
    "    val pe1_ready  = Input(Bool())\n",
    "    val pe1_data   = Output(UInt(16.W))\n",
    "  })\n",
    "\n",
    "  ???\n",
    "}\n",
    "\n",
    "test(new Arbiter) { c =>\n",
    "  import scala.util.Random\n",
    "  val data = Random.nextInt(65536)\n",
    "  c.io.fifo_data.poke(data.U)\n",
    "  \n",
    "  for (i <- 0 until 8) {\n",
    "    c.io.fifo_valid.poke((((i >> 0) % 2) != 0).B)\n",
    "    c.io.pe0_ready.poke((((i >> 1) % 2) != 0).B)\n",
    "    c.io.pe1_ready.poke((((i >> 2) % 2) != 0).B)\n",
    "\n",
    "    c.io.fifo_ready.expect((i > 1).B)\n",
    "    c.io.pe0_valid.expect((i == 3 || i == 7).B)\n",
    "    c.io.pe1_valid.expect((i == 5).B)\n",
    "    \n",
    "    if (i == 3 || i ==7) {\n",
    "      c.io.pe0_data.expect((data).U)\n",
    "    } else if (i == 5) {\n",
    "      c.io.pe1_data.expect((data).U)\n",
    "    }\n",
    "  }\n",
    "}\n",
    "println(\"SUCCESS!!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-2\" />\n",
    "<label for=\"check-2\"><strong>Solution</strong></label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "  io.fifo_ready := io.pe0_ready || io.pe1_ready\n",
    "  io.pe0_valid := io.fifo_valid && io.pe0_ready\n",
    "  io.pe1_valid := io.fifo_valid && io.pe1_ready && !io.pe0_ready\n",
    "  io.pe0_data := io.fifo_data\n",
    "  io.pe1_data := io.fifo_data\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">**Exercise: Parameterized Adder (Optional)**</span><br>\n",
    "This optional exercise exposes you to one of the most powerful features of Chisel, it's parameterization capabilities. To demonstrate this, we'll construct a parameterized adder that can either saturate the output when overflow occurs, or truncate the results (i.e. wrap around).\n",
    "\n",
    "First, look at the `Module` below. The parameter we pass into it is called `saturate` and has type *Scala* `Boolean`. This is not a Chisel `Bool`. So, we're not creating a single hardware adder that can either saturate or truncate, but rather we're creating a *generator* that produces either a saturating hardware adder *or* a truncating hardware adder. The decision is made at compile time.\n",
    "\n",
    "Next, notice the inputs and outputs are all 4-bit `UInt`s. Chisel has built-in width inferencing, and if you look at the [cheatsheet](https://github.com/freechipsproject/chisel-cheatsheet/releases/latest/download/chisel_cheatsheet.pdf), you'll see that the bitwidth of a normal summation is equal to the maximum bitwidth of the two inputs. This means that\n",
    "\n",
    "```scala\n",
    "val sum = io.in_a + io.in_b\n",
    "```\n",
    "\n",
    "will make `sum` a 4-bit wire, and the value will be the truncated result for 4-bit inputs. To check if the summation should saturate, you need to place the result in a 5-bit wire. This can be done with the `+&` summation, as seen on the cheatsheet.\n",
    "\n",
    "```scala\n",
    "val sum = io.in_a +& io.in_b\n",
    "```\n",
    "\n",
    "Finally, note that connecting a 4-bit `UInt` wire to a 5-bit `UInt` wire will truncate the MSB by default. You can use this to easily truncate the 5-bit sum for the non-saturating adder."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ParameterizedAdder(saturate: Boolean) extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in_a = Input(UInt(4.W))\n",
    "    val in_b = Input(UInt(4.W))\n",
    "    val out  = Output(UInt(4.W))\n",
    "  })\n",
    "\n",
    "  ???\n",
    "}\n",
    "\n",
    "for (saturate <- Seq(true, false)) {\n",
    "  test(new ParameterizedAdder(saturate)) { c =>\n",
    "    // 100 random tests\n",
    "    val cycles = 100\n",
    "    import scala.util.Random\n",
    "    import scala.math.min\n",
    "    for (i <- 0 until cycles) {\n",
    "      val in_a = Random.nextInt(16)\n",
    "      val in_b = Random.nextInt(16)\n",
    "      c.io.in_a.poke(in_a.U)\n",
    "      c.io.in_b.poke(in_b.U)\n",
    "      if (saturate) {\n",
    "        c.io.out.expect(min(in_a + in_b, 15).U)\n",
    "      } else {\n",
    "        c.io.out.expect(((in_a + in_b) % 16).U)\n",
    "      }\n",
    "    }\n",
    "    \n",
    "    // ensure we test saturation vs. truncation\n",
    "    c.io.in_a.poke(15.U)\n",
    "    c.io.in_b.poke(15.U)\n",
    "    if (saturate) {\n",
    "      c.io.out.expect(15.U)\n",
    "    } else {\n",
    "      c.io.out.expect(14.U)\n",
    "    }\n",
    "  }\n",
    "}\n",
    "println(\"SUCCESS!!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-3\" />\n",
    "<label for=\"check-3\"><strong>Solution</strong></label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "  val sum = io.in_a +& io.in_b\n",
    "  if (saturate) {\n",
    "    io.out := Mux(sum > 15.U, 15.U, sum)\n",
    "  } else {\n",
    "    io.out := sum\n",
    "  }\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# You're done!\n",
    "\n",
    "[Return to the top.](#top)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.12.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}